Review of Java is complete

Now begin study of data structures



What's a Data Structure?

	object that stores a collection of other objects
	data structures are often referred to as "collections"


The study of data structures has two points of view:

	(1) Using
	    Abstract interface provided by each data structure
		a. Called an "Abstract Data Type"
		b. Usually represented as a Java interface
	(2) Implementing
	    Various techniques for implementing the data structure


The next several lectures focus on using:

	(1) the various data structures
	(2) how they can be used to solve some representative problems
	(3) how to use implementations provided in the Java library


The next few projects involve solving problems using data structures.


What data types are included in the Java library?

	Collection, List, Set, SortedSet, 
	ArrayList, LinkedList, TreeSet, HashSet


What's a Collection?

	represents a group of objects


6.3.1 Collection Interface

public interface Collection {
	int size();
	void clear();
	boolean isEmpty();
	boolean add(Object x);
	boolean remove(Object x);
	boolean contains(Object x);
	Object[] toArray();
	Iterator iterator();
}


What classes implement Collection?

	ArrayList, LinkedList, TreeSet, HashSet


How are data structures the same?

	Collection defines common behaviors of the data structures

	Collection defines a set of methods that should be provided 
	    by any class that implements a data structure


How are data structures different?

	(1) order (List, Stack, Queue)
	    no order (Set)
	(2) duplicates (List, Stack, Queue)
	    no duplicats (Set)
	(3) access
	    (Stack = LIFO, Queue = FIFO, List = position)


What does the Collection interface allow you to do?

	access different data structures using the same interface


When would you use a Collection?

	when you want to write generic code that works on any data structure


DEMO	(Demo1.java)

	make ArrayList of Strings (names)
	make HashSet of Integers
	demo add, remove, contains




What's an Iterator?

	object that allows access to each object in a collection


Why do you need an Iterator?
Why can't you use a simple loop and array index approach?

	for (int i = 0; i < a.length; i++)
	    System.out.println (a[i]);

	don't know internal structure of a Collection


6.3.2 Iterator Interface

public interface Iterator {
	boolean hasNext();
	Object next();
	void remove();
}


How do you create an Iterator?

	Collection bag;
	Iterator i = bag.iterator();


Why is a factory method needed?
Why not 'new Iterator()' ?


How do you use an Iterator?

	while (i.hasNext())
	    System.out.println (i.next());


DEMO	(Demo1.java)

	write method to find maximum value in a Collection
	show that it works with different types of Collections